package leetcode_701_800;

import java.util.*;

public class LeeCode_756 {
    public static void main(String[] args) {
        List<String> all = new ArrayList<>();
        all.add("AAB");
        all.add("AAC");
        all.add("BCD");
        all.add("BBE");
        all.add("DEF");
        all.add("EDA");
        System.out.println(pyramidTransition("AAAA", all));
    }
    private static boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String, Set<Character>> map = new HashMap<>();
        for (String s : allowed) {
            String key = s.substring(0, 2);
            char val = s.charAt(2);
            if (map.containsKey(key)){
                map.get(key).add(val);
            }else {
                Set<Character> set = new HashSet<>();
                set.add(val);
                map.put(key, set);
            }
        }
        return f(map, new HashSet<>(), bottom);
    }
    private static boolean f(Map<String, Set<Character>> map, Set<String> failed, String now){
        if (now.length() == 1)
            return true;
        if (failed.contains(now)){
            return false;
        }
        Set<String> set = new HashSet<>();
        dfs(map, set, now, 0, "");
        if (set.isEmpty()){
            return false;
        }
        for (String s : set) {
            if (f(map, failed, s)){
                return true;
            }
            failed.add(s);
        }
        return false;
    }
    private static void dfs(Map<String, Set<Character>> map, Set<String> set, String bottom, int index, String now){
        if (index == bottom.length() - 1){
            set.add(now);
            return;
        }
        String key = bottom.substring(index, index + 2);
        if (!map.containsKey(key)){
            return;
        }
        for (Character c : map.get(key)) {
            dfs(map, set, bottom, index + 1, now + c);
        }
    }
}